This invention is a computer composed of numerous processor/memory units connected in the form of a tree, and intended for the efficient execution of applicative programming languages. In recent years, it has become possible to put one or more processing units and memory units on a single chip of silicon and to make numerous identical copies of such a chip at a small unit price. Given this technology, it is natural to try to combine many processors and memory units to obtain a powerful general-purpose computer. It is not obvious, though, how they should be connected, nor how they can be organized to cooperate with each other.
One promising approach is that proposed recently by Mago in U.S. Pat. No. 4,251,861 and in "A network of microprocessors to execute reduction languages," two parts, International Journal of Computer and Information Sciences 8, 5 (October 1979) and 8, 6 (December 1979). His computer architecture is designed specifically to execute an applicative programming language such as the Formal Functional Programming (FFP) languages introduced by Backus in "Can programming be liberated from the von Neumann style? A functional style and its algebra of programs," Communications of the ACM 21, 8 (August 1978), 613-641. These documents by Mago and by Backus are incorporated here by reference. An FFP language is defined by a small set of syntactic and semantic rules, with useful mathematical properties for reasoning about programs written in the language. FFPs are applicative (expression-oriented) rather than imperative (statement-oriented). There are no variables and no statements. Powerful operators can be built from simpler operators in a uniform style not possible in conventional programming languages. Most importantly, parallelism is easily and naturally expressed.
The machine disclosed here, like Mago's machine, can execute many programs simultaneously, and it can perform in parallel many operations below the level expressed in the program, since a single "primitive" FFP operation may be composed of more basic machine operations, some of which can be executed in parallel.
The machine disclosed here has been previously described in Tolle's Ph.D. dissertation, "Coordination of Computation in a Binary Tree of Processors: an Architectural Proposal," Department of Computer Science, the University of North Carolina at Chapel Hill, April 1981. That document is incorporated here by reference.
Since the invention described here is related to Mago's machine, it is necessary to discuss some of the details of his design. Before that is possible, the FFP languages must be described.